﻿#define  _CRT_SECURE_NO_WARNINGS 1


//19. 最⼤⼦数组和（medium）
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1);

        int ret = INT_MIN;
        for (int i = 1; i <= n; ++i)
        {
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            ret = max(dp[i], ret);
        }
        return ret;
    }
};

//20. 环形⼦数组的最⼤和（medium）
//1. 在中间 fmax
//2. 在两边 sum - 中间（gmin 最小值）

//f[i] 以 i 做结尾的「所有⼦数组」中和的最大值。
//g[i] 以 i 做结尾的「所有⼦数组」中和的最大值。

//全部为负数 导致 sum == gmin 相加为 0 非空数组表示应返回fmax 否则返回max(famx,sum-gmin) 
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        int gmin = INT_MAX, fmax = INT_MIN, sum = 0;
        for (int i = 1; i <= n; ++i)
        {
            f[i] = max(nums[i - 1], f[i - 1] + nums[i - 1]);
            g[i] = min(nums[i - 1], g[i - 1] + nums[i - 1]);

            fmax = max(f[i], fmax);
            gmin = min(g[i], gmin);

            sum += nums[i - 1];
        }

        return sum == gmin ? fmax : max(fmax, sum - gmin);
    }
};

//21. 乘积最⼤⼦数组（medium）

//只要1个 nums[i-1];
//大于一个  大于0(* fmax)  小于0 (*gmin) 取最大值    三者取最大值
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1, 1), g(n + 1, 1);

        int ret = INT_MIN;

        for (int i = 1; i <= n; ++i)
        {
            int x = nums[i - 1], y = nums[i - 1] * f[i - 1], z = nums[i - 1] * g[i - 1];
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));

            ret = max(f[i], ret);
        }
        return ret;
    }
};


//22. 乘积为正数的最⻓⼦数组（medium）
//f[i] 表⽰以 i 结尾的⼦数组，乘积为正数的最⻓⼦数组的⻓度。
//g[i] 以 i 结尾的所有⼦数组中，乘积为「负数」的最⻓⼦数组的⻓度。
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);

        int ret = INT_MIN;
        for (int i = 1; i <= n; ++i)
        {
            if (nums[i - 1] > 0)
            {
                f[i] = f[i - 1] + 1;
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;  //负为0 来个正数依然为0
            }
            else if (nums[i - 1] < 0)
            {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1; // 前面负数为0 不能相乘得正
                g[i] = f[i - 1] + 1;
            }
            ret = max(f[i], ret);
        }
        return ret;
    }
};